home *** CD-ROM | disk | FTP | other *** search
/ Shareware Super Platinum 8 / Shareware Super Platinum 8.iso / mac / DIAGTOOL / JPRDY101.ZIP;1 / RQSTSORT.TXT < prev    next >
Encoding:
Text File  |  1993-08-11  |  11.0 KB  |  255 lines
  1.               Disk Cache Request Sorting
  2.    The dangers of changing the order of disk writes
  3.  
  4. Introduction
  5.  
  6. At least three leading disk caches on the commercial software
  7. market attempt to enhance a PC's performance by changing the
  8. order that information is written to a disk.  Instead of
  9. processing disk writes on a first-in-first-out (FIFO) basis,
  10. these caches use request sorting.  Request sorting can reduce
  11. the elapsed time required to complete a series of disk writes,
  12. but it can also create periods of jeopardy that result in the
  13. corruption of a disk's file allocation information as well as
  14. a loss of data.
  15.  
  16. PC-Kwik Corporation has developed a diagnostic program that
  17. monitors a specific directory for these periods of jeopardy.
  18. When the directory and the file-allocation information become
  19. at risk, the user is alerted to the problem.
  20.  
  21. PC-Kwik's disk cache, Super PC-Kwik, provides request sorting
  22. as an option but does not use this technique as a default.
  23. Instead, it processes write requests on a FIFO basis,
  24. minimizing risk while still providing a dramatic performance
  25. gain.  Other caches expose the user's disk to the risk of
  26. corruption by defaulting to request sorting.  Often when the
  27. request sorting feature is turned off, the performance gain
  28. provided by these other caches decreases dramatically.
  29.  
  30.  
  31. History
  32.  
  33. Sorting the order of requests is a common technique for
  34. enhancing the throughput of a disk subsystem.  Time can be
  35. saved if the data is written to the desired sectors with less
  36. overall movement of the disk drive's heads.  Request sorting
  37. algorithms were originally designed for mainframes under the
  38. assumption that all requested input-output (I/O) would be
  39. completed.  This conclusion was based on three assumptions:
  40.  
  41. 1. I/O is under the control of a protected operating system
  42.    (i.e., not subject to failure due to bugs in application code).
  43. 2. The hardware operates with an uninterruptable power source.
  44. 3. The system is being operated by trained technicians.
  45.  
  46.  
  47. Request Sorting in the PC Environment
  48.  
  49. While these assumptions are typically valid for mainframe
  50. systems, they are not usually valid for DOS-based PCs.  Instead,
  51. we are all too familiar with frequent system crashes due to
  52. application bugs.  Most of us have accidentally rebooted or
  53. powered down our systems by hitting the reset button or the
  54. power switch at the wrong time.  And most of us have also
  55. experienced system failures due to power fluctuations.  When
  56. request sorting is not used, the impact of these problems is
  57. limited to the potential loss of the new data being written,
  58. instead of threatening the integrity of entire disk structures
  59. and databases.
  60.  
  61. Impact of Request Sorting on Database Systems
  62.  
  63. The designers of sophisticated PC database systems understand
  64. that their database update algorithms will sometimes be subject
  65. to system crashes.  To minimize the damage that these crashes
  66. produce, they carefully order the sequence of disk writes
  67. used to update index and data records (or their equivalent).
  68. Because of this careful ordering, the database software or
  69. utilities provided with it can usually recover from system
  70. failures by detecting how far database transactions proceeded
  71. before the failure, and limit the damage to the records not
  72. yet written.  When the order of modifications to the database
  73. is changed by a disk cache, the recovery procedure cannot
  74. accurately determine which transactions and substeps were
  75. completed, compromising the integrity of the entire database.
  76. Due to this unrecoverable damage that request sorting can cause
  77. here, most database users do not feel the performance increment
  78. is worth the risk.
  79.  
  80.  
  81. Risk vs. Reward
  82.  
  83. A sophisticated user will occasionally choose to accept the
  84. risks of request sorting to obtain the advantage of additional
  85. performance based on their knowledge that the application
  86. environment is largely bug free, an uninterruptable power
  87. supply is being provided, and the system will not be turned
  88. off or rebooted during the database transactions.  A careful
  89. user will also take the precaution of making regular backups
  90. of systems if they employ request sorting.
  91.  
  92. Unfortunately, though, there are many unsophisticated users
  93. using request sorting because most disk caches use request
  94. sorting algorithms by default.  The user is given little or
  95. no information about this risky technology and what the
  96. trade-offs are between performance and data integrity.
  97.  
  98.  
  99. The Impact of Request Sorting on Disk Structures
  100.  
  101. The DOS File Allocation Table (FAT) and directory structures
  102. can be thought of as a special type of database.  When DOS
  103. creates a file, it carefully postpones pointing the new
  104. directory entry at the newly allocated disk clusters until
  105. the FAT contains the required information about these clusters.
  106.  
  107. If a request sorting disk cache is used, there may be periods
  108. of time when directory entries point to disk clusters that are
  109. marked as unallocated in the FAT.  If the system is rebooted
  110. due to an application crash or a power failure during one of
  111. these jeopardy periods, the directory entry will continue to
  112. point to unallocated space on the disk.  If the system continues
  113. to be used, the same space will be allocated to another file,
  114. and cross-linked files will result.  Cross-linked files are
  115. almost impossible to correct, because two files end up sharing
  116. the same space on the disk.  One or both of the files will be
  117. corrupted, and there is no reliable technique for recovering
  118. the lost data.  A hard drive with many cross-linked files is
  119. typically referred to as "crashed."
  120.  
  121. Unfortunately, some disk caches reorder the sequence of disk
  122. writes so radically that directory/FAT structure are exposed
  123. to this type of jeopardy for long periods at a time.  Most
  124. users have no knowledge that they are incurring this type of
  125. risk, because the request sorting is the default mode.  Those
  126. who are aware of the situation are faced with either accepting
  127. the risk or disabling the caching of writes all together.
  128.  
  129.  
  130. Jeopardy Detection
  131.  
  132. To determine how often jeopardy periods are generated by
  133. various disk cache programs, PC-Kwik Corporation developed a
  134. Jeopardy Detection program.   This program continuously
  135. monitors the writing of sectors to a particular disk.  It
  136. compares the directory entries of a specific directory to
  137. the space shown as allocated in the FAT.  When it detects a
  138. discrepancy it alerts the user by changing the screen's border
  139. color to red.  The resulting flashing red border gives the
  140. user a sense of how often jeopardy periods occur for a
  141. particular directory.
  142.  
  143.  
  144. Disk Caches that Impose Jeopardy Periods
  145.  
  146. Most commercially available disk products default to using
  147. some form of request sorting.  According to our analysis,
  148. some of those which create periods of jeopardy include:
  149.  
  150. -- SMARTDrive which is included with Microsoft Windows 3.1
  151.    and DOS 6.0
  152.  
  153. -- NCache2 which is included with Norton Utilities 7.0
  154.  
  155. -- PC-Cache which is included with PC-Tools 8.0
  156.  
  157. We expect that many other disk cache programs generate the
  158. same sort of risk.
  159.  
  160.  
  161. Summary
  162.  
  163. The Super PC-Kwik disk cache defaults to strict FIFO processing
  164. of disk writes.  It provides a dramatic improvement in
  165. throughput without incurring the risks of request sorting.
  166. Sophisticated users have the option of reading documentation
  167. about advanced options like request sorting, time-delayed
  168. writes, and quick return of the DOS prompt.  They can then
  169. make an informed decision about which of these options are
  170. appropriate for their situation.
  171.  
  172.  
  173.                        FIGURE 1
  174.  
  175.   File Allocation Table               Directory
  176. +------------------------+       +---------------------+
  177. |                        |       |                     |
  178. |                        |       +---------------------+
  179. |                        |       | 1STFILE.DAT     +   |
  180. |        [Allocated]     |       +-----------------|---+
  181. |             |          |       |                 |   |
  182. +-------------|----------+       +-----------------|---+
  183.               |                                    |
  184.               |     +------------------------------+
  185.               |     |
  186.               |     V
  187.               |    +------------------------------+
  188.               +--->|  disk space                  |
  189.                    +------------------------------+
  190.  
  191. Figure 1.  File 1STFILE.DAT occupies space on the disk.  Space is
  192. allocated in the File Allocation Table and the file name has a
  193. directory which points to this space.
  194.  
  195.  
  196.                          FIGURE 2
  197.  
  198.   File Allocation Table               Directory
  199. +------------------------+       +---------------------+
  200. |                        |       |                     |
  201. |                        |       +---------------------+
  202. |                        |       | 1STFILE.DAT     +   |
  203. |        [Unallocated]   |       +-----------------|---+
  204. |                        |       |                 |   |
  205. +------------------------+       +-----------------|---+
  206.                                                    |
  207.                     +------------------------------+
  208.                     |
  209.                     V
  210.                    +------------------------------+
  211.                    |  disk space                  |
  212.                    +------------------------------+
  213.  
  214. Figure 2.  During a jeopardy period, file 1STFILE.DAT has a
  215. directory entry, but is not allocated in the FILE Allocation
  216. Table.  If a crash occurs during this jeopardy period, the disk
  217. space wil remain unallocated.
  218.  
  219.  
  220.                          FIGURE 3
  221.  
  222.   File Allocation Table               Directory
  223. +------------------------+       +---------------------+
  224. |                        |       |                     |
  225. |                        |       +---------------------+
  226. |                        |       | 1STFILE.DAT     +   |
  227. |        [Allocated]     |       +-----------------|---+
  228. |             |          |       |                 |   |
  229. +-------------|----------+       +-----------------|---+
  230.               |      +-----------------------------+
  231.               |      |
  232.               |      |           +---------------------+
  233.               |      |           |                     |
  234.               |      |           +---------------------+
  235.               |      |           | 2NDFILE.DAT     +   |
  236.               |      |           +-----------------|---+
  237.               |      |           |                 |   |
  238.               |      |           +-----------------|---+
  239.               |      |                             +
  240.               |      | +---------------------------+
  241.               |      | |
  242.               |      V V
  243.               |     +------------------------------+
  244.               +---->|  disk space                  |
  245.                     +------------------------------+
  246.  
  247. Figure 3.  Crosslinked files.  After system recovery, new file
  248. 2NDFILE.DAT is created and unllocated space is assigned to it.
  249. 1STFILE.DAT and 2NDFILE.DAT now occupy the same physical location
  250. and both have directory entries.
  251.  
  252.  
  253. PC-Kwik is a registered trademark of PC-Kwik Corporation.
  254.  
  255.